#include <stdio.h>
#include <string.h>
//#include <algorithm>

//using namespace std;

const int BASE = 1000000000; /* podstawa */
#define DIGS 9 /* liczba cyfr dziesietnych kazdej cyfry w zapisie
         przy powyzszej podstawie */
#define LEN 1000 /* stala dlugosc liczb */

const states[2][3][3] = {{{0,0,0},{1,0,0},{0,1,1}},{{1,0,0},{0,1,1},{0,0,1}}};

typedef struct t_liczba
{
	int t[LEN];
	int l; /* faktyczna dlugosc liczby */
} liczba;

int max(int a, int b)
{
	return (a > b) ? a : b;
}

void czytaj(liczba *x, char *s)
{
	/* Ustalamy dlugosc liczby */
	int j = strlen(s); /* pozycja w lancuchu s */
	if (j % DIGS == 0)
		x->l = j / DIGS;
	else
		x->l = j / DIGS + 1;
	j--;
	int i,k;
	for (i = 0; i < x->l; i++)
	{
		/* ustalamy i-ta cyfre */
		x->t[i] = 0;
		for (k = max(0, j - DIGS + 1); k <= j; k++)
		x->t[i] = 10 * x->t[i] + (s[k] - '0');
		j -= DIGS;
	}
}


void wypisz(liczba x)
{
	printf("%d", x.t[x.l - 1]);
	int i;
	for (i = x.l - 2; i >= 0; i--)
	printf("%0*d", DIGS, x.t[i]);
}

liczba div(liczba x, int y)
{
	liczba z;
	int c = 0; /* przeniesienie */
	z.l = x.l;
	int i;
	for (i = x.l - 1; i >= 0; i--)
	{
		z.t[i] = (int)(((long long)(c) * BASE + (long long)x.t[i]) / y);
		c = (int)(((long long)(c) * BASE + (long long)x.t[i]) % y);
	}

	/* Usuwamy ewentualne nowopowstale zera wiodace */
	while (z.l > 1 && z.t[z.l - 1] == 0)
		z.l--;
		
	return z;
}

int mod(liczba *x, int y)
{
	long long z = (long long)(x->t[x->l - 1]) % y;
	int i;
	for (i = x->l - 2; i >= 0; i--)
		z = (z * BASE + x->t[i]) % y;
	return (int)(z);
}

//s=d2-d1
void find_code(char *d1,char *d2,char *n,int l)
{
	int i,c=0;
	for(i=l-1;i>=0;i--)
	{
		d2[i+1]=states[c][n[i]][0];
		d1[i]=states[c][n[i]][1];
		c=states[c][n[i]][2];
	}
	d2[i+1]=c;
//	if(c==1)printf("%d dddd\n",i);
}

int main()
{
	liczba x,c;
	int d,i=0,j,z,N;
	char t[201],d1[201],d2[201];
	char s[LEN * DIGS + 1];
	scanf("%d",&N);	
	while(N--)
	{
		i=0;
		scanf("%s", s); /* czytamy lancuch - zakladamy, ze nie ma zer wiodacych */
		czytaj(&x,s);
		c=x;
		//scanf("%d",&d);
		while(x.l>1||x.t[0]>0)
		{
			//wypisz(x);
			//printf("%d",mod(&x,3));
			t[i++]=mod(&x,3);
			x=div(x,3);
		}
	
		char tmp;
		for(j=0;j<i/2;j++)
		{
			tmp=t[j];
			t[j]=t[i-1-j];
			t[i-1-j]=tmp;
		}		
	
		find_code(d1,d2,t,i);
	
		z=0;
		for(j=0;j<=i;j++)if(d2[j]==1)z++;
		printf("%d ", z);
		for(j=i;j>=0;j--)if(d2[j]==1)printf("%d ",i-j);
		printf("\n");

		z=0;
		for(j=0;j<i;j++)if(d1[j]==1)z++;
		printf("%d ", z);
		for(j=i-1;j>=0;j--)if(d1[j]==1)printf("%d ",i-1-j);
		printf("\n");
		
		/*
		for(j=0;j<i;j++)printf("%c",t[j]+'0');
		printf("\n");
		for(j=0;j<=i;j++)printf("%c",d2[j]+'0');	
		printf("\n");
		for(j=0;j<i;j++)printf("%c",d1[j]+'0');	
		printf("\n");
		*/
		//wypisz(c);
	
	}
	
	return 0;
}
